import java.util.HashSet;
import java.util.Set;

/**
 * @Author: wzp
 * @CreateTime: 2024-09-21  10:40
 * @Description: 零钱兑换
 * @Version: 1.0
 */
public class q_322 {
    public int coinChange(int[] coins, int amount) {

        if(amount==0){
            return 0;
        }
//        将coins存储到list里面
        Set<Integer> set=new HashSet<>();
        for (int coin : coins) {
            set.add(coin);
        }
        int[] dp=new int[amount+1];
        dp[1]=set.contains(1)?1:-1;
        for (int i = 1; i <= amount; i++) {
            int temp_min=Integer.MAX_VALUE;
            for (int j = 0; j <=i/2 ; j++) {
                if(j==0){
                    if(set.contains(i)){
                        temp_min=1;
                        break;
                    }else {
                        continue;
                    }
                }
                if(dp[j]==-1||dp[i-j]==-1){
                    continue;
                }else{
                    temp_min=Math.min(temp_min,dp[j]+dp[i-j]);
                }

            }
            dp[i]=temp_min==Integer.MAX_VALUE?-1:temp_min;
        }
        return dp[amount];

    }

    public static void main(String[] args) {
//        [1,2,5]
        int[] coins={1,2,5};
        int amount=11;
        q_322 q322=new q_322();
        System.out.println(q322.coinChange(coins,amount));

    }
}
